package com.cn.algorithm.one.map;

import java.util.Comparator;


/*
* 跳表：实现和维护简单，搜索、添加、删除的时间复杂度都使O(log n)级别
* */
public class SkipList<K, V> {

    public static final int MAX_LEVEL = 32;

    /*
    * 概率因子，是否增加高层的概率
    **/
    public static final float P = 0.25f;

    int size;

    int level;

    Node<K, V> first;

    Comparator<K> comparator;


    public SkipList() {
        first = new Node<>(null, null, MAX_LEVEL);
    }

    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public void clear() {
        first = null;
        size = 0;
        level = 0;
    }

    public V get(K key) {
        Node<K, V> node = node(key);
        return node == null ? null : node.value;
    }

    public boolean containsKey(K key) {
        return node(key) != null;
    }

    public V put(K key, V value) {
        Node<K, V> node = first;
        int cmp = -1;
        Node<K, V>[] prev = new Node[level];
        for (int i = level - 1; i >= 0; i--) {
            while (node.next[i] != null && (cmp = compare(key, node.next[i].key)) > 0) {
                node = node.next[i];
            }
            if (cmp == 0) {
                V oldValue = node.next[i].value;
                node.next[i].value = value;
                return oldValue;
            }
            prev[i] = node;
        }
        int newLevel = getNewLevel();
        Node<K, V> newNode = new Node<>(key, value, newLevel);
        for (int i = newLevel - 1; i >= 0; i--) {
            if (i >= level) {
                first.next[i] = newNode;
            } else {
                newNode.next[i] = prev[i].next[i];
                prev[i].next[i] = newNode;
            }
        }
        level = Math.max(level, newLevel);
        size++;
        return null;
    }

    public V remove(K key) {
        Node<K, V> node = first;
        Node<K, V>[] prev = new Node[level];
        int cmp = -1;
        boolean exists = false;
        for (int i = level - 1; i >= 0; i--) {
            while (node.next[i] != null && (cmp = compare(key, node.next[i].key)) > 0) {
                node = node.next[i];
            }
            if (cmp == 0) {
                exists = true;
            }
            prev[i] = node;
        }
        if (!exists) {
            return null;
        }
        Node<K, V> removeNode = node.next[0];
        V oldValue = removeNode.value;
        for (int i = 0; i < removeNode.next.length; i++) {
            prev[i].next[i] = removeNode.next[i];
        }
        int tmp = level;
        while (first.next[tmp - 1] == null && tmp > 0) {
            tmp--;
        }
        level = tmp;
        size--;
        return oldValue;

    }

    public int getNewLevel() {
        int tmp = 1;
        while (P < Math.random() && tmp < MAX_LEVEL) {
            tmp++;
        }
        return tmp;
    }


    public Node<K, V> node(K key) {
        Node<K, V> node = first;
        int cmp = -1;
        for (int i = level - 1; i >= 0; i--) {
            while (node.next[i] != null && (cmp = compare(key, node.next[i].key)) > 0) {
                node = node.next[i];
            }
            if (cmp == 0) {
                return node.next[i];
            }
        }
        return null;
    }

    public int compare(K k1, K k2) {
        return comparator == null ? ((Comparable<K>) k1).compareTo(k2) : comparator.compare(k1, k2);
    }


    public static class Node<K, V> {

        K key;

        V value;

        Node<K, V>[] next;

        public Node(K key, V value, int level) {
            this.key = key;
            this.value = value;
            this.next = new Node[level];
        }
    }


    public static void main(String[] args) {
        SkipList<Integer, Integer> list = new SkipList<>();
        for (int i = 0; i < 10; i++) {
            list.put(i, i);
        }
        System.out.println(list.size());

        for (int i= 0; i < 3; i++) {
            System.out.println(list.remove(i));;
        }
        for (int i = 0; i < 10; i++) {
            System.out.println(list.get(i));
        }
        System.out.println(list.size());
    }
}
